package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T1143 {
    public static void main(String[] args) {
        System.out.println(new T1143().longestCommonSubsequence("abcde", "aced"));
        System.out.println(new T1143().longestCommonSubsequence2("abcde", "aced"));
    }

    public int longestCommonSubsequence2(String text1, String text2) {
        int[][] cache = new int[text1.length()][text2.length()];
        cache[0][0] = text1.charAt(0) == text2.charAt(0) ? 1 : 0;
        for (int i = 0; i < text1.length(); i++) {
            for (int j = 0; j < text2.length(); j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                if (text1.charAt(i) == text2.charAt(j)) {
                    cache[i][j] = get(cache, i - 1, j - 1) + 1;
                } else {
                    cache[i][j] = Math.max(get(cache, i - 1, j), get(cache, i, j - 1));
                }
            }
        }
        return cache[text1.length()-1][text2.length()-1];
    }
    private void print(int[][]dp){
        System.out.println("===");
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("===");
    }
    private int get(int[][] dp, int i, int j) {
        if (i < 0 || j < 0) {
            return 0;
        }
        return dp[i][j];
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] cache = new int[text1.length()][text2.length()];
        for (int[] ints : cache) {
            Arrays.fill(ints, -1);
        }
        return longestCommonSubsequence(text1, text2,
                text1.length() - 1, text2.length() - 1, cache);
    }

    public int longestCommonSubsequence(String text1, String text2, int i, int j, int[][] cache) {
        if (i < 0 || j < 0) {
            return 0;
        }
        if (cache[i][j] != -1) {
            return cache[i][j];
        }
        int ans = -1;
        if (i == 0 && j == 0) {
            ans = text1.charAt(0) == text2.charAt(0) ? 1 : 0;
        } else {
            if (text1.charAt(i) == text2.charAt(j)) {
                ans = longestCommonSubsequence(text1, text2, i - 1, j - 1, cache) + 1;
            } else {
                ans = Math.max(longestCommonSubsequence(text1, text2, i - 1, j, cache), longestCommonSubsequence(text1, text2, i, j - 1, cache));
            }
        }
        cache[i][j] = ans;
        return ans;
    }
}
